__author__ = 'st316'
'''
Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space.
You may not modify the values in the list, only nodes itself can be changed.
'''


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def toString(self):
        cur = self
        s = ''
        while cur.next:
            s += str(cur.val) + ' -> '
            cur = cur.next
        return s + str(cur.val)


class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        if not head or not head.next:
            return head
        p = head
        q = p.next
        r = q.next
        head = q
        while True:
            if not r:
                q.next = p
                p.next = None
                break
            elif not r.next:
                p.next = r
                q.next = p
                break
            else:
                p.next = r.next
                q.next = p
                p = r
                q = p.next
                r = q.next
        return head


if __name__ == '__main__':
    s = Solution()
    l = [1, 3, 3, 1, 3, 1, 3, 3, 2, 3, 2]
    ll = ListNode(l[0])
    cur = ll
    for v in l[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    print s.swapPairs(ll).toString()